/*
 * @lc app=leetcode id=133 lang=cpp
 *
 * [133] Clone Graph
 */
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return node;
        }

        unordered_map<Node*, Node*> visited;

        Node *newNode = new Node();
        newNode->val = node->val;
        visited[node] = newNode;

        cloneGraph(node, newNode, visited);
        return newNode;
    }

    void cloneGraph(Node* node, Node* newNode, unordered_map<Node*, Node*>& visited) {

        for (auto n : node->neighbors) {
            if (!visited[n]) {
                Node *next = new Node();
                next->val = n->val;
                visited[n] = next;
                cloneGraph(n, next, visited);
            }
            newNode->neighbors.push_back(visited[n]);
        }
    }

};

